The present invention generally relates to organizing data structures on a storage medium. More specifically, the invention relates to a method and apparatus for optimizing the layout of data structures on a disc, such as a DVD disc.
An example of a DVD specification for a Read-Only Disc is published by Toshiba Corporation.
Such specifications ensure interoperability among different hardware implementations for accessing data on a DVD disc. Any optical DVD disc conforming to open video specifications and containing the correct video formatting can be played or read by any DVD player that was designed to play DVDs conforming to that open-format DVD specification. The general techniques for organizing ensembles on DVD media and the standards used are described in DVD Demystified, by J. Taylor, McGraw Hill (1988), Chapters 3 and 4 as well as the particular DVD specification.
Unlike consumer VCR""s where navigation commands such as xe2x80x9cplayxe2x80x9d, xe2x80x9cforwardxe2x80x9d and xe2x80x9creversexe2x80x9d are a function of the hardware playback device, in the context of DVD discs, the navigation command structures are programmed in during the authoring stage (disc organization) and embedded in the disc. As a result, compressing audio and video does not by itself create a DVD; the compression merely provides video and audio files for the authoring process.
A sophisticated tool is required to assemble the content and create interactivity. This is known as DVD premastering and represents one of the most complex DVD disc organization tasks.
Authoring includes the processes that are performed (after video and audio encoding are performed) at what is generally known as a post house, and before disc replication at a stamping facility. It is the process in which, for example, the encoded audio and video are linked together, multiple language tracks are laid out, subtitles are imported or generated, chapter points and transport control functions are introduced, multi-story or multi-angle program chains are created, menus and buttons are designed, etc..
The first step is to lay out the disc in a storyboard that shows all of the disc elements plus all of the menus and navigation steps that will join the disc elements together as a seamless work. The storyboard process serves three main purposes: to provide a roadmap for different designers working on the same project, to avoid errors in disc element assembly and menu creation; as a checklist to minimize rework; and as a xe2x80x9cpreflightxe2x80x9d navigation check to avoid dead ends, confusing or overly complicated menus, or inconsistent and user-unfriendly disc navigation.
The end result of the storyboard process is a complete roadmap of the work on the DVD disc, as well as a bit budget and disc element capture list.
The next step is to assemble all of the source elements that have been captured: MPEG video, audio, graphics, sub-titles, and sub-pictures. These elementary files are liked together into objects with one or more video angle files associated with one or more audio clips and sub-picture clips. The objects are usually not multiplexed (interleaved) until the project is complete.
Importing stills for menus and creating highlight areas, colors and xe2x80x9chot spotsxe2x80x9d for buttons can be one of the most labor-intensive aspects of the process. It is essential to have a knowledge of multimedia programming and a graphical interface for sub-picture assembly that allows control over features such as fades, wipes, button activation times and highlights.
Once all the objects have been assembled, scene flow links are created to give the work interactivity. In this process, the pre and post-commands are set and links are made between the various disc elements. Still or motion video may be used as menus.
With all the navigation data and presentation data complete, the final project is then laid out. In this process all the presentation data (video, audio, and sub-pictures) are multiplexed together. The end result is a new set of files, which comply with the basic DVD format.
The last stage in DVD authoring is to create the disc image, a process by which the DVD files are formatted to a standard file system. This disc image is initially created on hard disc for proofing.
The above process describes an exemplary prior art method for creating basic DVD discs. However, advances in technology, such as for example the DIVX DVD, have enhanced basic DVDs by adding additional features, thereby enabling firmware applications and other multimedia applications to coexist on a DVD disc. However, these additional.-features on enhanced DVD disc come at the cost of an increase in storage used. The increase in storage results from the addition of data files and application files used to support the additional features.
The data layout for DVD discs in accordance with prior art systems as described above is very convoluted, possibly resulting in a multitude of links between the files on the disc. As the number of files increases, and the size of the files become larger, seek time is increased. However, with an increase in seek time, the quality of use of such systems is decreased resulting in a xe2x80x9cdead imagexe2x80x9d when retrieving the next element in a scene.
What is needed is a method and apparatus for organizing data files on a DVD disc so as to minimize dead images when retrieving the next element in a scene.
The method and apparatus for Disc Layout and Optimization (DLO) in accordance with the present invention receives input such as a list of disc elements, a list of scene links, compiled code files, and still media files. The DLO also preferably obtains information, e.g., from a work order, regarding the size of the target DVD disc, the number of layers on the disc, and whether the disc is a dual layer disc, the type of tracking used, i.e., parallel or opposite, etc. Furthermore the DLO also preferably obtains an estimate of the amount of disc space used by all items except the JARs (files that contains other files). This allows a single disc request to load related files in a short amount of time. Files in a JAR may contain any type of data. The amount of disc space used by all items except the JARs, includes the file systems, open content (non-limiting examples include commercials), media content (non-limiting examples include movies), etc.
JARs from a scene code builder are authored to perform a specific application, e.g., movie play or catalog. A JAR may also contain code classes and/or static media. When a disc is loaded into a player, a JAR or multiple JARs are loaded into RAM in the player in order to interact with a user.
A player may be any system or device capable of reading a medium having a plurality of elements linked by a scene flow. Applications on disc which may have linked items may include movies, games, or any interactive elements. In a preferred embodiment of the present invention, the data elements include movie content and interactive video elements, and are used merely to facilitate the function of the invention, and is not intended to limit the scope or application of the invention to other data elements. Likewise, in a preferred embodiment of the present invention, the player is a DVD player, which is used merely to facilitate the function of the invention, and is not intended to limit the scope or application of the invention to other players, such as computers or video game players.
A scene is made up of one or more JARs. The JARs in a scene are hierarchical. This means that a JAR may only call a JAR immediately below it. All JARs in the hierarchy remain in memory for the duration of the scene. The JARs that remain in memory are called transaction JARs. Transaction JARs are used as a shared memory area to pass information between scenes. Transactions may be nested creating distinct shared memory areas.
The navigation information from the scene code builder informs the DLO of the JAR types and scene flow. This allows the program to arrange the JARs and content to minimize the elapsed time between scenes. To accomplish this, a called JAR is placed within a reasonable distance of its calling JAR. If necessary, JARs will be replicated on the disc so as to keep the elapsed time as short as possible. Part of the scene flow information tells the DLO when a transaction JAR is unloaded. This facilitates memory computations.
The DLO is also aware of memory constraints, defined by players on the market, which information is passed as a configuration parameter from a configuration file. The DLO will not build a disc layout that it believes will exceed the memory available to it. Preferably, memory checking may be disabled through a configuration parameter.
It is an object of the present invention to solve the deficiencies of the prior art in the field of DVD disc layout. Specifically, it is an object of the present invention to create and arrange JAR files and data files so as to minimize the elapsed time between scenes as perceived by the user.
It is yet another object of the present invention to provide a method and system for optimizing a disc layout containing data files, firmware applications, and multimedia applications so as to minimize seek time between elements on the disc.
To achieve the foregoing and other objects and in accordance with the purpose of the present invention, as embodied and broadly described herein, the method for optimizing a disc layout having disc elements and scene links of this invention may comprise the steps of reading the disc elements, reading the scene links, creating implicit links between at least two scene links, and the implicit links, and replicating at least one of the disc elements onto the initial layout thereby creating a modified layout.
In a preferred embodiment of the present invention, the method for optimizing a disc layout further comprises the step of creating navigation tables having sector addresses for each disc element and sector addresses for replications of each disc element.
In another preferred embodiment of the present invention, the step of creating implicit links between at least two scene links further comprises the step of expanding a disc element thereby identifying the disc elements"" links.
In yet another preferred embodiment of the present invention, the method for optimizing a disc layout further comprises the step of creating firmware JARs.
In still another preferred embodiment of the present invention, the method for optimizing a disc layout further comprises the step of determining if the disc is an opposite track dual layer disc. Particularly, when the disc is determined to be an opposite track dual layer disc, the method for optimizing a disc layout further comprises the step of determining whether the addition of the item will move a split point on the disc. More particularly, when the addition of the item is determined to move the split point on the disc, the method for optimizing a disc layout further comprises the step of moving the split point on the disc.
In general, another aspect of the present invention features a method for optimizing a disc layout having disc elements and scene links comprising the steps of reading the disc elements, reading the scene links, creating implicit links between at least two scene links, performing an initial layout of the disc elements, the scene links, and the implicit links, replicating at least one of the disc elements onto the initial layout thereby creating a modified layout; and removing at least one disc element from the modified layout.
In general, yet another aspect of the present invention features a method for optimizing a disc layout according to layout having disc elements and scene links comprising the steps of reading the disc elements, reading the scene links, creating implicit links between at least two scene links, performing an initial layout of the disc elements, the scene links, and the implicit links, replicating at least one of the disc elements onto the initial layout thereby creating a modified layout, removing at least one disc element from the modified layout, and performing a final layout of the disc elements, the scene links, and the implicit links.
In a preferred embodiment of the present invention, the method for optimizing a disc layout further comprises the step of determining whether any scene links or implicit links are larger than a predetermined memory.
In general, still another aspect of the present invention features a computer system for optimizing a disc layout having disc elements and scene links comprising a means for reading the disc elements, a means for reading the scene links, a means for creating implicit links between at least two scene links, a means for performing an initial layout of the disc elements, the scene links, and the implicit links, a means for replicating at least one of the disc elements onto the initial layout to create a modified layout.
In a preferred embodiment of the present invention, the computer system further comprises a means for removing at least one disc element form the modified layout. Preferably, the computer system further comprises a means for performing a final layout of the disc elements, the scene links and the implicit links.
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.